//给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 
//
// 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。 
//
// 
//
// 示例 1: 
//
// 
//输入: s = "cbaebabacd", p = "abc"
//输出: [0,6]
//解释:
//起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
//起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
// 
//
// 示例 2: 
//
// 
//输入: s = "abab", p = "ab"
//输出: [0,1,2]
//解释:
//起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
//起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
//起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
// 
//
// 
//
// 提示: 
//
// 
// 1 <= s.length, p.length <= 3 * 10⁴ 
// s 和 p 仅包含小写字母 
// 
//
// Related Topics 哈希表 字符串 滑动窗口 👍 1451 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2024-06-05 11:33:47
 * @description 438.找到字符串中所有字母异位词
 */
public class FindAllAnagramsInAString{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 FindAllAnagramsInAString fun=new FindAllAnagramsInAString();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
 class Solution {
	/*超时*/
	public List<Integer> findAnagrams(String s, String p) {
		List<Integer> res = new ArrayList<>();
		//计算匹配串排序后的hashcode
		char[] chars = p.toCharArray();
		Arrays.sort(chars);
		int code = Arrays.toString(chars).hashCode();

		Set<Character> set = new HashSet<>();
		for (char ch : chars) {
			set.add(ch);
		}

		for (int i = 0, k = 0; i < s.length()-p.length()+1; ) {
			//如果这个字母在set中
			k=i;
			while (set.contains(s.charAt(k))) {
				//如果匹配长度完全
				if (k-i+1 == p.length()) {
					//如果code 相等保存答案
					char[] subchar = s.substring(i, k+1).toCharArray();
					Arrays.sort(subchar);
					if (code == Arrays.toString(subchar).hashCode()) {
						//保存答案
						res.add(i);
					}
					//因为每一位都在set中，所以进一位,同时更新k的值
					++i;
					break;
					//没匹配完就继续匹配下一位
				} else {
					k++;
				}
			}
			//防止跳出while循环时，hash不匹配的情况也加k
			if(!set.contains(s.charAt(k))){
				//不包含的情况下，则调到k的下一位
				i = k + 1;
			}

		}

		return res;
	}
	/*滑动窗口 利用Arrays.equals
    * 时间复杂度：O(m+(n−m)×Σ)，其中 nn 为字符串 ss 的长度，mm 为字符串 pp 的长度，
    * Σ 为所有可能的字符数。
    空间复杂度：O(Σ)。用于存储字符串 pp 和滑动窗口中每种字母的数量
*/
	public List<Integer> findAnagrams2(String s, String p) {
		int slen = s.length();
		int plen = p.length();
		if(plen>slen) {
			return  new ArrayList<Integer>();
		}
		List<Integer> res = new ArrayList<Integer>();
		int[] sCount = new int[26];
		int[] pCount = new int[26];
		//先初始化
		for (int i = 0; i < plen; i++) {
			++sCount[s.charAt(i)-'a'];
			++pCount[p.charAt(i)-'a'];
		}
		if (Arrays.equals(sCount, pCount)) {
			res.add(0);
		}

		for (int i = 0; i < slen - plen; ++i) {
			--sCount[s.charAt(i) - 'a'];
			++sCount[s.charAt(i + plen) - 'a'];

			if (Arrays.equals(sCount, pCount)) {
				res.add(i + 1);
			}
		}
		return res;
	}
	/*
	 * 滑动窗口优化
	 * 用差值来代表是否还能继续前进当不能前进时*/
	public List<Integer> findAnagrams1(String s, String p) {
		int [] c=new int[128];
		//先初始化数组，把匹配串对应的字母标记次数
		for(char ch:p.toCharArray()) c[ch]++;
		int l=0,r=0;
		List<Integer> res = new ArrayList<>();
		while(r<s.length()){
			//如果当前位置存在于匹配串种，消耗掉当前的位置，然后右边的位置往前
			if(c[s.charAt(r)]>0){
				c[s.charAt(r++)]--;
				//如果消耗到匹配的长度，就记录
				if(r-l==p.length()) res.add(l);
				//如果不匹配，说明右移左边界，复位计数器，直到条件再次满足
				//p种的资源相当于存粮，r没有见到存粮时，l会补给，补给后，r会立即消耗往前走
				//如果r遇见是存粮x中的子集x1中的一部分，后面r没有遇见存粮就不动了，l会立即补给x1个
				//即l只会比r快一步，最大可能慢x步

				// 找完一次异位词，其实就正好将count数组中的频次全部消耗为0
				// 此时右指针来到一个非p字符，或者虽然是p字符但count中已经没有频次可消耗了，于是赖着不走了
				// 左指针出动，开始为count数组作补给，
				// 对于非p字符，左指针补一口，右指针就吃一口，亦步亦趋，直到再次遇到p中字符，右指针才可能反超，
				// 注意，此时右指针消耗的频次，其实来自于左指针从前一个异位词那里补充的
			}else {
				//非匹配的串，消耗一个存一个，匹配的字符，消耗完一次会马上补充
				c[s.charAt(l++)]++;
			}
		}
		return  res;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
